# 运用你所掌握的数据结构，设计和实现一个 LRU (最近最少使用) 缓存机制 。 
# 
#  
#  
#  实现 LRUCache 类： 
# 
#  
#  LRUCache(int capacity) 以正整数作为容量 capacity 初始化 LRU 缓存 
#  int get(int key) 如果关键字 key 存在于缓存中，则返回关键字的值，否则返回 -1 。 
#  void put(int key, int value) 如果关键字已经存在，则变更其数据值；如果关键字不存在，则插入该组「关键字-值」。当缓存容量达到上
# 限时，它应该在写入新数据之前删除最久未使用的数据值，从而为新的数据值留出空间。 
#  
# 
#  
#  
#  
# 
#  进阶：你是否可以在 O(1) 时间复杂度内完成这两种操作？ 
# 
#  
# 
#  示例： 
# 
#  
# 输入
# ["LRUCache", "put", "put", "get", "put", "get", "put", "get", "get", "get"]
# [[2], [1, 1], [2, 2], [1], [3, 3], [2], [4, 4], [1], [3], [4]]
# 输出
# [null, null, null, 1, null, -1, null, -1, 3, 4]
# 
# 解释
# LRUCache lRUCache = new LRUCache(2);
# lRUCache.put(1, 1); // 缓存是 {1=1}
# lRUCache.put(2, 2); // 缓存是 {1=1, 2=2}
# lRUCache.get(1);    // 返回 1
# lRUCache.put(3, 3); // 该操作会使得关键字 2 作废，缓存是 {1=1, 3=3}
# lRUCache.get(2);    // 返回 -1 (未找到)
# lRUCache.put(4, 4); // 该操作会使得关键字 1 作废，缓存是 {4=4, 3=3}
# lRUCache.get(1);    // 返回 -1 (未找到)
# lRUCache.get(3);    // 返回 3
# lRUCache.get(4);    // 返回 4
#  
# 
#  
# 
#  提示： 
# 
#  
#  1 <= capacity <= 3000 
#  0 <= key <= 10000 
#  0 <= value <= 105 
#  最多调用 2 * 105 次 get 和 put 
#  
#  Related Topics 设计 哈希表 链表 双向链表 
#  👍 1642 👎 0
import collections
from typing import List


# leetcode submit region begin(Prohibit modification and deletion)

class LinkedNode:
    def __init__(self, key=0, value=0):
        self.key = key
        self.value = value
        self.prev = None
        self.next = None


class LRUCache:

    def __init__(self, capacity: int):
        self.cache = dict()
        self.head = LinkedNode()
        self.tail = LinkedNode()
        self.head.next = self.tail
        self.tail.next = self.head
        self.size = 0
        self.capacity = capacity

    def get(self, key: int) -> int:
        if key not in self.cache:
            return -1
        node = self.cache[key]
        self.move_to_head(node)
        return node.value

    def put(self, key: int, value: int) -> None:
        if key in self.cache:
            node = self.cache[key]
            node.value = value
            self.move_to_head(node)
        else:
            node = LinkedNode(key, value)
            self.cache[key] = node
            self.add_head(node)
            self.size += 1
            if self.size > self.capacity:
                tail = self.remove_tail()
                # 移除链表节点后, 需要在缓存中删除
                self.cache.pop(tail.key)
                self.size -= 1

    def remove_node(self, node: LinkedNode):
        node.prev.next = node.next
        node.next.prev = node.prev

    def move_to_head(self, node: LinkedNode):
        self.remove_node(node)
        self.add_head(node)

    def add_head(self, node: LinkedNode):
        next = self.head.next
        self.head.next = node
        node.prev = self.head
        node.next = next
        next.prev = node

    def remove_tail(self):
        tail = self.tail.prev
        self.remove_node(tail)
        return tail


# Your LRUCache object will be instantiated and called as such:
# obj = LRUCache(capacity)
# param_1 = obj.get(key)
# obj.put(key,value)
# leetcode submit region end(Prohibit modification and deletion)


def log(*args, **kwargs):
    print(*args, **kwargs)


# 语言自带
# python OrderedDict
# Java LinkedHashMap
# class LRUCache(collections.OrderedDict):
#
#     def __init__(self, capacity: int):
#         super().__init__()
#         self.capacity = capacity
#
#     def get(self, key: int) -> int:
#         if key not in self:
#             return -1
#         self.move_to_end(key)
#         return self[key]
#
#     def put(self, key: int, value: int) -> None:
#         if key in self:
#             self.move_to_end(key)
#         self[key] = value
#         if len(self) > self.capacity:
#             self.popitem(False)

# 哈希表, 双链表
# 双链表节点储存k, v, 头节点最近被使用, 尾节点最近都没用
# cache 里放 node
# 节点移动到头: 先删除节点, 再在头节点插入
#
# class LRUCache:
#
#     def __init__(self, capacity: int):
#         self.cache = dict()
#         # 虚拟头尾节点
#         self.head = LinkedNode()
#         self.tail = LinkedNode()
#         self.head.next = self.tail
#         self.tail.next = self.head
#         self.capacity = capacity
#         self.size = 0
#
#     def get(self, key: int) -> int:
#         if key not in self.cache:
#             return -1
#         self.move_to_head(self.cache[key])
#         return self.cache[key].value
#
#     def put(self, key: int, value: int) -> None:
#         if key in self.cache:
#             node = self.cache[key]
#             node.value = value
#             self.move_to_head(self.cache[key])
#         else:
#             node = LinkedNode(key, value)
#             self.cache[key] = node
#             self.add_head(node)
#             self.size += 1
#             if self.size > self.capacity:
#                 tail = self.remove_tail()
#                 self.cache.pop(tail.key)
#                 self.size -= 1
#
#     def remove_node(self, node: LinkedNode):
#         node.prev.next = node.next
#         node.next.prev = node.prev
#
#     def add_head(self, node):
#         next = self.head.next
#         self.head.next = node
#         node.prev = self.head
#         node.next = next
#         next.prev = node
#
#     def remove_tail(self):
#         node = self.tail.prev
#         self.remove_node(node)
#         return node
#
#     def move_to_head(self, node: LinkedNode):
#         self.remove_node(node)
#         self.add_head(node)

if __name__ == '__main__':
    lRUCache = LRUCache(2)
    lRUCache.put(1, 1)
    item1 = lRUCache.get(1)
    assert item1 == 1, item1
    lRUCache.put(2, 2)
    lRUCache.put(3, 3)
    assert lRUCache.get(1) == -1, lRUCache.get(1)
    item2 = lRUCache.get(2)
    lRUCache.put(4, 4)
    assert lRUCache.get(3) == -1, lRUCache.get(3)
